Nearly all forms of electronic communication and storage systems use error-correcting codes. Error correcting codes compensate for the intrinsic unreliability of information transfer in these systems by introducing redundancy into the data stream. The mathematical foundations of error correcting were established by Shannon. Shannon developed the mathematical concept of the channel in which distortion of signals in communications systems is modeled as a random process. The most fundamental result of Shannon is the Noisy channel theorem, which defines for the channel a capacity, a quantity that specifies the maximum rate at which information can be reliably delivered through the channel. Reliable transmission at rates approaching capacity requires the use of error correcting codes. Thus, error-correcting codes are designed to achieve sufficient reliability while approaching capacity as closely as possible. The complexity of implementing the error correcting code is an additional factor that comes into play in practical applications of error correcting codes. Recent advances in error correcting coding systems resulting from the invention of turbo codes and the subsequent rediscovery and development of low-density parity-check (LDPC) codes offer coding systems of feasible complexity that can approach Shannon's capacity quite closely.
LDPC codes are well represented by bipartite graphs, often called Tanner graphs, such as the graph 100 shown in FIG. 1. In Tanner graphs in one set of nodes, the variable nodes 102, corresponds to bits of the codeword and the other set of nodes, the constraint nodes 106, sometimes called check nodes, correspond to the set of parity-check constraints which define the code. Edges 104 in the graph connect variable nodes to constraint nodes. A variable node and a constraint node are said to be neighbors if they are connected by an edge in the graph. One typically assumes that a pair of nodes is connected by at most one edge. LDPC codes can equivalently be represented using the parity check matrix 202. FIG. 2 presents an example of a parity matrix representation where the indicated vector x 208 is a codeword if and only if Hx=0.
To each variable node is associated one bit of the codeword. In some cases some of these bits might be punctured. Punctured bits may be desirable in certain code structures and they are excluded from the transmitted codeword.
A bit sequence associated one-to-one with the variable node sequence is a codeword of the code if and only if, for each constraint node, the bits neighboring the constraint (via their association with variable nodes) sum to zero modulo two, i.e., they comprise an even number of ones.
The decoders and decoding algorithms used to decode LDPC codewords operate by exchanging messages within the graph along the edges and updating these messages by performing computations at the nodes based on the incoming messages. Such algorithms will be generally referred to as message passing algorithms. Each variable node in the graph is initially provided with a soft bit, termed a received value, that indicates an estimate of the associated bit's value as determined by observations from, e.g., the communications channel. Ideally, the estimates for separate bits are statistically independent. This ideal can be, and often is, violated in practice. A collection of received values constitutes a received word. For purposes of this application we may identify the signal observed by, e.g., the receiver in a communications system, with the received word.
The number of edges attached to a node, i.e., a variable node or constraint node, is referred to as the degree of the node. A regular graph or code is one for which all variable nodes have the same degree, j say, and all constraint nodes have the same degree, k say. In this case we say that the code is a (j,k) regular code. These were the codes considered originally by Gallager (1961). In contrast to a “regular” code, an irregular code has constraint nodes and/or variable nodes of differing degrees. For example, some variable nodes may be of degree 4, others of degree 3 and still others of degree 2.
While irregular codes can be more complicated to represent and/or implement, it has been shown that irregular LDPC codes can provide superior error correction/detection performance when compared to regular LDPC codes.
It will be appreciated that received words generated in conjunction with LDPC coding, can be processed by performing LDPC decoding operations thereon, e.g., error correction and detection operations, to generate a reconstructed version of the original codeword. The reconstructed codeword can then be subject to data decoding to recover the original data that was coded. The data decoding process may be, e.g., simply selecting a specific subset of the bits from the reconstructed codeword.
As mentioned above, LDPC decoding operations generally comprise message passing algorithms. There are many potentially useful message passing algorithms and the use of such algorithms is not limited to LDPC decoding
To facilitate understanding of the invention discussed in the sections which follow, we will now give a brief mathematical description of belief propagation.
Belief propagation for (binary) LDPC codes can be expressed as follows. Messages transmitted along the edges of the graph are interpreted as log-likelihoods log P0/P1 for the bit associated to the variable node. Here, (p0,p1) represents a conditional probability distribution on the associated bit where px denotes the probability that the bit takes the value x. The soft bits provided to the decoder by the receiver are also given in the form of a log-likelihood. Thus, the received values, i.e., the elements of the received word, are log-likelihoods of the associated bits conditioned on the observation of the bits provided by the communication channel. In general, a message m represents the log-likelihood m and a received value y represents the log-likelihood y. For punctured bits the log-likelihood received value y is set to 0, indicating p0=p1=½.
Let us consider the message-passing rules of belief propagation. Messages are denoted by mC2V for messages from check nodes to variable nodes and by mV2C for messages from variable nodes to check nodes. Consider a variable node with d edges. For each edge j=1, . . . ,d let mC2V (i) denote the incoming message on edge i. At the initialization of the decoding process we set mC2V=0 for every edge. In general, outgoing messages from variable nodes are given bymV2C(j)=y+(Σi=1dmC2V(i))−mC2V(j).The outgoing decoded soft value from a node (not an edge message) corresponding to this operation is given by Xout=y+(Σi=1dmC2V(i)). The outgoing hard decision associated to this output is obtained from the sign of xout.
At the check nodes it is often more convenient to represent the messages using their ‘sign’ and magnitudes. Thus, for a message m let mp ∈GF[2] denote the ‘parity’ of the message, i.e., mp=0 if m≧0 and mp=1 if m<0. Additionally let mr ∈[0,∞] denote the magnitude of m. Thus, we have m=−1mp mr. At the check node the updates for mp and mr are separate. We have, for a check node of degree d,mpC2V(j)=(Σi=1dmpV2C(i))−mpV2C(j),
where all addition is over GF[2], andmrC2V(j)=F−1((Σi=1dF(mrV2C(i)))−F(mrV2C(j))),where addition is real and we define F(x):=ln coth (x/2). We note that F is its own inverse, i.e., F−1(x)=F(x).
An algorithm often mentioned in LDPC literature is the so-called MIN-SUM algorithm. In this algorithm the update operation at check nodes can be expressed mathematically asmrC2V(j)=min{(∪i=1dmrV2C(i))\mrV2C(j)}.Thus, the reliability of a C2V message is equal to the minimum reliability of the V2C messages incoming along other edges. To implement this algorithm it is sufficient to save at the check node the smallest and second smallest reliability (they may be the same value if that value occurs for at least two incoming messages) and the identity of the edge providing the incoming message of least reliability. The reliability of the outgoing C2V message on the edge originating the least reliable incoming message is equal to the second smallest incoming reliability and the reliability of the outgoing C2V message on all other edges is equal to the smallest reliability.
In the U.S. Pat. No. 6,633,856 an LDPC decoder architecture was described. In that architecture the messages being sent from check nodes to variable nodes were stored in memory. If the messages comprise 5 bits, for example, and a check node has degree K, then the storage used for those messages is 5K bits.
From an implementation and cost standpoint it is generally desirable to implement an LDPC decoder in a manner that is relatively simple to construct and requires a relatively small amount of hardware. Memory is a major component in many decoder designs. It would be desirable if the amount of memory required to implement a decoder could be keep to a low or minimal amount to thereby reduce hardware costs.
While memory reduction is of a concern, in reducing the amount of memory used, it is often necessary to avoid a design which would impose unacceptable processing delays which might result in the failure to meet one or more real world decoding time constraints.
In view of the above discussion, it should be apparent that memory efficient methods and apparatus which can be used to simply the implementation of LDPC decoders and/or produce an LDPC decoder capable of performing decoding operations with a relatively small amount of memory would be desirable. In addition, methods for avoiding the introduction of extensive delays into an LDPC decoding process using a memory efficient decoder implementation are desirable and would be beneficial.